package com.mamingchao.foundation.tree.heap;

import java.util.Arrays;

/**
 * Created by mlamp on 2024/5/13.
 * 已知一个几乎有序的数组。几乎有序，是指如果把数组排好顺序，每个元素的移动距离一定不超过K步，并且K相对于数组长度来讲是比较小的
 * 请选择一个合适的排序测列，对这个数组进行排序
 *
 * 举个例子，比如 K==5
 * [            ]
 * 0 1 2 3 4 5 6
 * 从0到5的元素，视为一个堆结构，调整顺序为一个最小堆；调整之后，0位置的数据即为 0~5之间最小的，也是整个数组最小的；
 * 因为如果 index == 6位置的数据，比前五 都小，就不满足 题干所述，【把整个排好序，每个元素的移动距离不超过K步】
 * 把 1~6位置的元素视为一个堆结构，调整顺序为最小堆；调整之后，1位置即为 1~6之间的最小值，也是整个数组除了0位置之外所有元素的最小值
 * 周而复始，最终得到一个排好顺序的
 *
 * 堆排序，即先用一个高时间复杂度()的heapInsert ，把整个数组做成大根堆
 * 然后 因为用了大根堆最后的一个值替换了整个树的根，所以这棵树不再是大根堆；
 * 这个时候用 时间复杂度比较低的 heapify，从上到下只调整一条path，即可把 树重新调整为大根堆；即 heapify
 */

public class HeapSortIssue1 {
//    private static int[] almostSortedArray = {2,3,1,6,4,9,8,5};
    private static int[] almostSortedArray = {2,3,1, 6,4,9};

    public static void main(String[] args) {
        final int k = 5;
        HeapifyUtil heapifyUtil = HeapifyUtil.getInstance();

        int loop = almostSortedArray.length > 5 ? almostSortedArray.length-k+1 : 1;

        for (int i = 1; i <= loop; i++) {

//            int[] subArr = Arrays.copyOfRange(almostSortedArray, i , i + k);
            // 如果 堆数组长度 超过5，则计算生成 子堆数组的endIndex；如果堆数组长度 不超过5，endIndex 就是 堆数组的长度 +1
            // 我们这里使用左闭右开的区间，所以后面的 almostSortedArray.length 还需要加个1
            int endIndex = almostSortedArray.length > 5 ? i + k : almostSortedArray.length +1;


            // 这个还有些问题，回头再调把
            for (int myIndex = endIndex -1 ; myIndex >= i; myIndex--) {
                heapifyUtil.heapify(almostSortedArray, myIndex, i, endIndex, 1);
//                heapifyUtil.heapify(almostSortedArray, myIndex, i, endIndex, 0);
            }



        }

        System.out.println(Arrays.toString(almostSortedArray));
    }


}
